package demo1;

import java.util.Arrays;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {//堆箱子
    public int pileBox(int[][] box) {
        Arrays.sort(box,(i, j)->{
            return i[0]-j[0];
        });
        int n = box.length;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = box[i][2];
        }
        int ret = 0;
        for (int i = 0; i < n; i++) {
            int max = dp[i];
            for (int j = 0; j < i; j++) {
                if(box[i][0]>box[j][0] && box[i][1]>box[j][1] && box[i][2]>box[j][2]){
                    max = Math.max(max,dp[j]+dp[i]);
                }
            }
            dp[i] = max;
            ret = Math.max(ret,max);
        }
        return ret;
    }

    //俄罗斯套娃信封问题
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes,(i,j)->{
            if(i[0]==j[0]){
                return j[1]-i[1];
            }
            return i[0]-j[0];
        });
        int len = envelopes.length;
        int[] ret = new int[len];
        ret[0] = envelopes[0][1];
        int size = 1;
        for (int i = 1; i < len; i++) {
            size = merg(ret,envelopes[i][1],size);
        }
        return size;
    }

    private int merg(int[] nums,int key,int size){
        int left = 0;int right = size-1;
        while (left < right) {
            int mid = left+(right-left)/2;
            if(nums[mid]<key) left = mid+1;
            else right = mid;
        }
        if(nums[left]<key && left==size-1){
            nums[left+1] = key;
            return size+1;
        }
        nums[left] = key;
        return size;
    }

    public int maxEnvelopes1(int[][] envelopes) {
        Arrays.sort(envelopes,(i,j)->{
            return i[0]-j[0];
        });
        int n = envelopes.length;
        int[] dp = new int[n];
        Arrays.fill(dp,1);
        dp[0] = 1;
        int MAX = 0;
        for (int i = 1; i < n; i++) {
            int max = Integer.MIN_VALUE;
            for (int j = 0; j < i; j++) {
                if(envelopes[i][0]>envelopes[j][0] && envelopes[i][1]>envelopes[j][1]){
                    max = Math.max(max,dp[j]);
                }
            }
            dp[i] = max+1;
            MAX = Math.max(MAX,dp[i]);
        }
        return MAX;
    }

    //K次乘运算后的最终数组1
    public int[] getFinalState(int[] nums, int k, int multiplier) {
        int n = nums.length;
        int minIndex = 0;
        for (int i = 0; i < k; i++) {
            minIndex = 0;
            for (int j = 0; j < n; j++) {
                if(nums[minIndex]>nums[j]){
                    minIndex = j;
                }
            }
            nums[minIndex] *= multiplier;
        }
        return nums;
    }
}
